#include "string_array.h"
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i+1];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i+1];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

myStr::myStr(const char* a){

    if(!a){ data = nullptr;
    next = nullptr;
    nextVal = nullptr;
    }
    else{
        int i =1;
    length = strlen(a);//只调用一次strlen，节省资源
    data = new char[length +1];
    data[0] = length;//开头存大小
    for(i; i <= length; i++){
        data[i] = a[i-1];//挨个赋值
        }
    }

}



myStr::~myStr(){
    if(!data){ data = nullptr;
    next = nullptr;
    length = 0;
    nextVal = nullptr;
    }//处理空串
    else{
        delete[] data;
        delete[] next;
        delete[] nextVal;
        length = 0;
    }
}

void myStr::kmp_next() {
 
    if(!data){
        return;
    }

    int i = 1;//后缀的最后一个字符
    next =  new int[length+1];//next数组
    next[0] = 0; 
    next[1] = 0;//因为从0开始打印，所以后面的全-1
    int j = 0;//前缀的最后一个
    while(i < length){
        if( j == 0 /*没东西可比*/|| data[i] == data[j]/*前后缀匹配了 */){
            i++;//移动到下一个字符，此时的i就是失效位
            j++;//移动到下一个
            next[i] = j;//最大的前后缀长度
        }
        else{j = next[j];}//不匹配了，就找前j个更短的前缀比
    }

}

void myStr::kmp_nextVal() {//next函数的修正数组
    if(!data){
        return;
    }
    int i = 1;
    int j = 0;
    nextVal = new int[length+1];
    nextVal[0] = 0;//防止出错
    nextVal[1] = 0;//初始化跟next数组相同,
    while(i < length){
        if(j == 0 || data[i] == data[j]){
            i++;
            j++;
            if(data[i] != data[j]){nextVal[i] = j;}//如果失效位跟前缀之后不等，正常
            else{nextVal[i] = nextVal[j];}//相等了，说明如果i真失效了，那j位肯定也会失效，  
        }                                 //所以nextval【i】的值只能是nextval【j】，     
                                          //因为nextval【j】位置的字符在之前验证过了，不等于j位置的字符，所以也不等于i位置的
        else{j = nextVal[j];}//不等就正常
    }                                     

}


int kmpMatch(const myStr& s, const myStr& t){
    if(s.data == nullptr || t.data == nullptr){return -1;}//空
   
    int i = 1;
    int j = 1;
    while(i <= s.length && j <= t.length){//防越界
        if(j == 0 || s.data[i] == t.data[j]){i++;j++;}//匹配或者next数组遇到0了
        else { j = t.nextVal[j];}

    }
    if(j > t.length) {return i - t.length;}//成功率，此时找到匹配位置了
    else{return -1;}
}

int simpleMatch(const myStr& s, const myStr& t){
//目标串S和模式串T，求T在S中的位置。匹配失败返回-1，匹配成功返回匹配位置
        if (s.data == nullptr || t.data == nullptr || s.length < t.length || t.length == 0) {
        return -1;
    }

   
    int i = 1; // i 是主串 s 中当前比较位置的索引
    int j = 1; // j 是模式串 t 中当前比较位置的索引
    
    
    while (i <= s.length && j <= t.length) {
        // 如果当前字符匹配成功
        if (s.data[i] == t.data[j]) {
            i++; // 主串和模式串都向后移动一位
            j++;
        } else {
            // 如果当前字符匹配失败
            i = i - j + 2; // 主串回溯：回到本次匹配开始位置的下一个位置
                          
            j = 1;         
        }
    }

    
    // 如果 j > t.length，成功了
    if (j > t.length) {
    
        return i - t.length;
    } else {
        // 失败
        return -1;
    }

}

bool replaceStr(myStr& s, const int& st, const myStr& t, const myStr& v){
    /*bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V)，即
    要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；
    若主串S中不存在子串T，则函数返回0， start取值从1开始*/
       

    if(s.data == nullptr || t.data == nullptr || v.data == nullptr){return 0;}//空
    int i = st; // i 是主串 S 中当前比较位置的索引
    int j = 1; // j 是模式串 T 中当前比较位置的索引
    int pos = 0;
    
    while (i <= s.length && j <= t.length) {
        // 如果当前字符匹配成功
        if (s.data[i] == t.data[j]) {
            i++; // 主串和模式串都向后移动一位
            j++;
        } else {
            // 如果当前字符匹配失败
            i = i - j + 2; // 主串回溯：回到本次匹配开始位置的下一个位置 
            j = 1;        
        }
    }
    if (j > t.length) {
        // 匹配成功的起始位置是 i - t.length 
        pos = i - t.length;
    } else {
     
        return 0;
    }
    int new_length = s.length - t.length + v.length;//新串长度

    // 分配新内存
    char* new_data = new char[new_length + 1]; 
    new_data[0] = new_length;

    
    // 复制前缀
    if (pos > 1) {
        memcpy(new_data + 1, s.data + 1, pos - 1);
    }

    //复制新子串 V
    if (v.length > 0) {
        memcpy(new_data + pos, v.data + 1, v.length);
    }

    //复制后缀,难算！
    int pos_1 = pos + t.length;//s剩下的后缀的起始位置
    int s_len = s.length - pos_1 + 1;//剩下的后缀长
    if (s_len > 0) {
        memcpy(new_data + pos + v.length, s.data + pos_1, s_len);
    }

    // 更新主串 s
    delete[] s.data;

    s.data = new_data;
    s.length = new_length;
    s.next = nullptr;
    s.nextVal = nullptr;

    return 1;



}


myMatrix::myMatrix(const int& rnum, const int& cnum , const int& n, const int* arr){
    /*初始化稀疏矩阵，myMatrix (const int& rNum, const int& cNum, const int& nNum,
     const int*),参数依次为行数、列数、三元组元素个数、三元组初始化数据，数组元素为3的倍数，
     每3个数一组，分别为（row，col，value）*/
    rowNum = rnum;
    colNum = cnum;
    nodeNum = n;

    if(n > 0){  
        nodeList = new matrixNode[n]; //一系列初始化操作
    int i = 0;
    for(i; i < n;++i){
        int r = i*3;
        int c = r+1;
        int nnum = c+1;//每一个元素的行，列，数
        nodeList[i].row = arr[r];
        nodeList[i].col = arr[c];
        nodeList[i].value = arr[nnum];
    }//三元组初始化
    }
    else{nodeList = nullptr;}
}





myMatrix::~myMatrix(){
    delete[] nodeList;

}

void myMatrix::FastTransposeSMatrix(myMatrix& t){
    //实现快速转置算法void FastTransposeSMatrix(myMatrix& T),转置结果存在T中
    if(nodeNum == 0){return;}//空
    t.rowNum = colNum;
    t.colNum = rowNum;//转置
    t.nodeNum = nodeNum;
    t.nodeList = new matrixNode[nodeNum];//初始化

    int* num = new int[colNum]();    // 初始化为 0：记录原矩阵每列非零元素个数
    int* cpot = new int[colNum]();   // 初始化为 0：记录转置矩阵每列第一个元素位置

    //接下来求这两个数组的值
    int i= 0;
    for(i; i < nodeNum; i++){
        num[nodeList[i].col]++;//求每一列的非零值
    }

    cpot[0] = 0;//规定
    //求第每一列第一个非零元素在转置矩阵的三元列表里的位置（索引）
    i = 1;
    for(i; i <colNum; ++i){
        cpot[i] = cpot[i - 1] + num[i-1];
    }

    //接下来求t
    int j;//存原矩阵的列数
    int k;//存cpot的值
    i = 0;
    for(i; i < nodeNum ; ++i){
        j = nodeList[i].col;
        k = cpot[j];
        t.nodeList[k].row = nodeList[i].col;
        t.nodeList[k].col = nodeList[i].row;
        t.nodeList[k].value = nodeList[i].value;
        cpot[j]++;//该列下一个非零元素在转置矩阵的三元列表里的位置（索引）
    }
        delete[] num;
        delete[] cpot;
        num = nullptr;
        cpot = nullptr;


}